/**
 * 738.单调递增的数字
 */
public class Exerciser10 {
    // 如：1,2,3,4,5,5,5,4,3,6,8,2
    // 遍历寻找第一个递减的位置，也就是数据为 5 这个位置的下标，到最后一个5，因为 5 > 4 递减
    // 因为和最后一个5 相邻的位置存在和其相等的值，那么就往前进行遍历，寻找到第一个为5 这个数据的位置
    // 之后把 第一个为 5 的位置的值进行 -1 之后把其后面所有的值设置为 9
    // 最后为：1,2,3,4,5,9,9,9,9,9,9,9
    public int monotoneIncreasingDigits(int n) {
        // 把int转换成 String容易进行处理
        char[] s = Integer.toString(n).toCharArray();

        int i = 0,m = s.length;
        // 这里就是贪
        // 找到最后一个递增的位置，也就是下一个位置为递减的值，就是 s[i] > s[i + 1]位置的下标
        // 这时候如果把 i前面的值进行减小的话，那么不是最大的，因为如果把前面进行减小，那么可以牵扯到原先的递增的位置的值，变为了递减，就不对了
        while(i + 1 < m && s[i] <= s[i + 1]) {
            // 查找第一个进行递减的情况下的 i位置
            i++;
        }
        // 处理一下特殊情况
        if(i == m - 1) {
            return n;
        }

        while(i - 1 >= 0 && s[i] == s[i - 1]) {
            // 把所有和i位置相等的值并且是和i位置相邻的值进行回退，找到第一个为s[i]的值
            i--;
        }

        // 之后把当前i位置的值进行 -1 ，并且将其后面的所有值都设置为9
        s[i]--;
        for(int j = i + 1;j < m;j++) {
            s[j] = '9';
        }

        return Integer.parseInt(new String(s));
    }
}
